Data storage devices, such as disk drives using shingled recording media and solid state drives, can use “logical block address (LBA) indirection” to store user data on non-volatile media, such as a disk surface or flash memory, wherein LBAs and associated data are not typically stored in the same physical location each time they are written. In a data storage device using LBA indirection, a host may write a logically sequential group of LBAs into a corresponding number of sequential physical locations on the non-volatile media. However, as the LBAs are rewritten by the host, they may end up in non-sequential physical locations. Thus, a group of LBAs that was once sequentially written onto the non-volatile media may become scattered at different locations on the media as they are rewritten. As a result, the non-volatile media will become increasingly fragmented over time, which can significantly degrade the read performance of the data storage device.
In addition, a data storage device that uses LBA indirection typically uses a translation table to keep track of LBAs and corresponding physical locations on the non-volatile media. As the non-volatile media becomes fragmented, the number of entries in the translation table increases, thereby undesirably increasing the amount of memory required to store the translation table.
To overcome the aforementioned problems associated with fragmentation of the non-volatile media, a defragmentation may be employed. In a defragmentation process, a range of LBAs may be selected, read from the non-volatile media (e.g., a shingled recording media), and rewritten as a sequential stream onto the non-volatile media. The above steps may be repeated for each LBA range on the non-volatile media. This process increases read performance of the non-volatile media and also reduces the size and required storage space of the translation table. However, the defragmentation process can be an expensive operation in that it can increase latency and reduce overall data storage device performance. Thus, it is important to perform the defragmentation process efficiently so as to minimize the aforementioned undesirable effects.